It has become increasingly useful to interconnect a plurality of data processing elements by means of a packet switching network in which data is transmitted as data assemblages called "packets". Such networks include a plurality of interconnected switching nodes which, in turn, are connected to end nodes supporting data processing equipments. Such packet networks can become quite large with an extensive geographical distribution. In such a situation, the selection of an efficient path between two end nodes which wish to communicate with each other becomes of paramount importance. Different methods are summarized by H. Nussbaumer in Teleinformatique II (pages 92 to 117) Presses Polytechniques Romandes 1987.
Path Selection
The general problem which must be solved at the network level is to find a path between a source and a destination node. When the network is using datagrams, the path selection must be done individually for each packet. For virtual circuits, the path decision is done once only at the time of the circuit establishment. In both cases, the choice of a routing algorithm is not easy because it must satisfy a large number of often conflicting requirements. This algorithm must be simple to implement to not complicate its implementation at the nodes; it must ensure a correct progress of the packets whatever the disturbance on the network. The algorithm must be able to provide satisfying results despite the traffic variations and variations in the network topology. It must also ensure equity between the different end users and provide an equal distribution of the rights to access the network. Finally, the routing algorithm must allow, when possible, optimal use of the network according to criterion which can vary with the utilization type. In most of the cases, the network is implemented in a way to minimize the packet transit time and to transfer the maximum number of packets. The principal objectives are respectively the reduction of the transit time and the increase of the throughput. In other cases, the objective is to decrease the communication cost, or to develop a reliable network able to operate correctly (without significant performance degradation) either in case of catastrophic line, or node failure or peaks of traffic.
Because of the variety of the constraints, there are a large number of different routing types. Some correspond to deterministic or adaptive policies according to their capacity of integrating the traffic variations and the network topology. Routing algorithms can be centralized if the paths are determined from a particular node. Others are distributed among all nodes; this is favorable in a reliability point of view but the algorithm is more complicated and the path optimization is more difficult to implement. Some algorithms are difficult to classify: they are using special techniques called Flooding Routing or Random Routing.
Flooding Routing
Flooding Routing is based on a very simple principle, consisting of each node retransmitting packets on all output links of the node, except the input link. A node connected to K other nodes retransmits K-1 copies of the packet which has been just received. This method allows the delivery to the destination node of at least one copy of the packet with one condition; namely, the destination node must exist on at least one path between the source and the destination node. Routing is ensured even when the network topology is changing, for example after a catastrophic failure of some components in the network. Flooding Routing allows robust use of the network resources. Furthermore, as all possible links between the source and the destination node are tried in an exhaustive way, the method ensures that at least one copy of the packet will reach the recipient through the shorter path with the minimum delay if the network is not overloaded. This technique is simple to implement since neither routing tables to route the messages, nor knowledge of the geographical position of the destination node in the network are required. The recipient must only know that the packet is addressed to it.
The price to pay for these qualities of robustness, simplicity and rapidity is a heavy utilization of the network resources and a tendency to congestion. Usually, it is advantageous to place in the packet header a field indicating the maximum number of nodes through which a packet is authorized to pass. This field is decremented each time the packet goes through a node, and packets with an empty field are discarded.
Random or Stochastic Routing
This technique, like Flooding Routing, does not demand the nodes have complete knowledge network structure and traffic to make a routing decision. However, here, to limit the generation of excessive ghost traffic, the nodes do not send systematically copies of the packets they receive over output links. Random Routing consists in sending one or more counterparts of the received packet on output links selected at random. This method is also called Selective Flooding. This policy leads to very simple routing at the node level and limits the saturation of the network due to packet duplication. In return, the average routing delay is longer than that resulting from deterministic techniques. Packets may take sinuous routes instead of taking the most direct path toward the destination node.
DETERMINISTIC ROUTING
Fixed Routing
Fixed Routing defines paths for different packets according to general network characteristics such as network topology and the mean traffic expected on the communication lines. The routing rules are established once and aim for optimizing performance based on criterion provided by the user. In most of the cases, the average packet transmission time through the network must be minimized. The method consists in building a routing table at the level of each node. Its consultation allows the node to determine on which output link the packet it has just received must be transferred. Fixed Routing is very simple in its principles. The only processing done in the nodes consists in queues management and tables reading and the optimization algorithm is initiated only once at the network design level. Fixed Routing aims for a long term and a global optimization of the network. In comparison with the random routing, this technique can considerably speed up packet transmission through the network.
Adaptive Routing
Contrary to the Fixed Routing, the purpose of Adaptive Routing is to satisfy optimization criterion in existance at any time. Tables are repeatedly updated according to, for example, the instantaneous state of the traffic on the lines.
Centralized Routing
When the characteristics of the network fluctuate, it is possible to adapt the routing by assigning to one node the responsibility of periodically updating routing tables according to traffic variations and changes in the topology. This method, simple in its principles, is called Centralized Routing. Its principal disadvantage is that it generates significant auxiliary traffic and subordinates the functioning of the network to only one node. The different nodes must send to the routing center the state of the network as they perceive it (operational adjacent nodes, traffic . . . ), and the routing center must, in its turn, dispatch to the nodes their routing tables. The auxiliary traffic is concentrated around the routing center, which results in saturation of this part of the network. Furthermore, the Centralized Routing can generate some problems at the time the tables are refreshed because said tables cannot be received at the same time by all the nodes. A solution is to decentralize the establishment of the tables to the level of each node.
Local Routing
Local and distributed routing methods are both based on the establishment by each node of its own routing table according to information locally collected. With the local routing technique, each node builds its table without exchanging information with the neighboring nodes. In its most simple form, the method consists in placing the packet just received in the shortest available output queue and in transmitting the packet as rapidly as possible. The local algorithm tends in its principle to circulate the packets very quickly in the network. However, the mean path lengths are far from minimal.
Distributed Routing
Distributed Routing is a local method in which neighboring nodes exchange messages concerning the traffic and the network condition to update their routing and delay tables.
Hierarchical Routing
With the Stochatic Routing methods, each node requires a table with as many rows as nodes in the network and a number of columns equal to the number of output links. Furthermore, when the routing is adaptive, nodes must exchange periodically messages to update their routing tables. The table sizes and the importance of the control message increase rapidly with the number of nodes and become unacceptable when the network contains more than ten nodes. To solve this problem, the network is divided in a hierarchy of sub networks as illustrated in FIG. 12. In particular, optimal clustering structures (003) are determined so as to minimize the length of the routing tables required. Each table takes into account only the nodes in one sub network (003) and a packet addressed to a node in another subnetwork will necessarily go through a transit node (005) for this remote sub network. Packets transit through mandatory nodes (005) and the price to pay for this simplification is that smaller routing tables give less precise routing information, which then results in longer path lengths for the message traffic. Hierarchical Routing procedures are particularly effective for large packet switched networks (001). With smaller routing tables, they require less storage and processing in the nodes (002) as well as less communications overhead in the links (004).
The problem of the optimization of hierarchical levels has been studied by L. Kleinrock and F. Kamoun--Hierarchical Routing For Large Networks, Computer Networks, Vol. 1, pp. 155-174, January 1977.
The main idea for reducing routing table length is to keep, at any node, complete routing information about nodes which are close to it and less information about nodes located further away from it. This can be realized by providing one entry per destination for the closer nodes and one entry per set of destinations for the remote nodes.
The reduction of routing table length is achieved through a hierarchical partitioning of the network. Basically, an m-level hierarchical clustering of a set of nodes (FIG. 12) consists in grouping the nodes (002) into a 1st level of clusters (003), which in turn, are grouped into 2nd level clusters etc. . . This operation continues in a bottom up fashion. The mth level cluster is the highest level cluster (3rd level cluster) and, as such, it includes all the nodes of the network (001).
Unfortunately, the reductions in table length are accompanied with an increase of the message path length in the network. This results in a degradation of network performance (delay, throughput) due to excess internal traffic caused by longer path length. However, in very large networks, an enormous table reduction may be achieved with no significant increase in network path length.
HIGH PERFORMANCE NETWORKS
Data transmission is now evolving with a specific focus on applications and by integrating a fundamental shift in the customer traffic profile. Driven by the growth of workstations, local area networks (LAN) interconnection, distributed processing between workstations and super computers, new applications and the integration of various and often conflicting structures--hierarchical versus peer to peer, wide (WAN) versus local (LAN) area networks, voice versus data--the data profile has become higher in bandwidth, bursty, nondeterministic and requires more connectivity. Based on the above, it is clear that there is strong requirement for supporting distributed computing applications across high speed networks that can carry LAN communications, voice, video, and traffic among channel attached hosts, business, engineering workstations, terminals, and small to intermediate file servers. This vision of a high speed multiprotocol network is the driver for the emergence of fast packet switching networks architectures in which data, voice, and video information is digitally encoded, chopped into small packets and transmitted through a common set of nodes and links.
Throughput
The key requirement of these new architectures is to reduce the end-to-end delay in order to satisfy real time delivery constraints and to achieve the necessary high nodal throughput for the transport of voice and video. Increases in link speeds have not been matched by proportionate increases in the processing speeds of communication nodes and the fundamental challenge for high speed networks is to minimize the packet processing time within each node. As example, for meeting a typical 100 ms delay limit to deliver a voice packet between two end users; a total of 36 ms might be needed for the packetization and play-out functions at the end points and about 20 ms is the unalterable propagation delay needed, say, to cross the United States.
There remains 44 ms for all the intra-node processing time as the packet moves through the network. In a 5 node network, each node would have about 8 ms for all processing time including any queueing time. In a 10 node network, each node would have about 4 ms.
Another way of looking the same constraint is illustrated in FIG. 1: taking a node with an effective processing rate of 1 MIPS (Millions of Instructions Per Second), it is possible to fill a 9.6 kbps line with 1000 byte packets even if a network node must execute 833 000 instructions per packet processed. For a 64 kbps line the node can afford 125 000 instructions per packet. In order to fill an OC24 link, however, a 1 MIPS node could only execute 7 instructions per packet. In the latter case, even an effective rate of 10-30 MIPS would allow only 70-200 instructions per packet.
In order to minimize the processing time and to take full advantage of the high speed/low error rate technologies, most of the transport and control functions provided by the new high bandwidth network architectures are performed on an end-to-end basis. The flow control and particularly the path selection are managed by the access points of the network which reduces both the awareness and the function of the intermediate nodes.
Routing Modes
Routing within the network presents two aspects:
1. Determining what the route for a given connection shall be, PA0 2. Actually switching the packet within a switching node.
There are many methods of determining a route through a network. For very high throughput, the critical item is that the switching elements must be able to decide where to route an incoming packet in a very short portion of time. As described in the document High Speed Networking Technology, an Introductory Survey (pages 88 to 96)--GG24-3816-00 ITSC Raleigh March 1992, the routing modes the most widely used are Source Routing and Label Swapping.
Source Routing
Source Routing is a particular implementation of Distributed Routing for connectionless networks. The source node (or access node) is responsible for calculating the route the packet must take through the network. A routing field is appended to every packet sent and that field is used by the intermediate nodes to direct the packet towards its destination. In this technique, the sending node must know the network topology and it must be able to find the optimal route. But once the route is determined, intermediate nodes do not need to refer to any tables or parameters to make the routing decision. The next stage of the route is in the packet header. A drawback of this method is that the routing field in the packet header takes some storage and is an overhead. But this is quite small and the benefits of being able to make a fast routing decision outweigh the small increase in bandwidth overhead. Since all routing information is contained in each packet, a setup is not required along the path to provide an end to end communication. Thus, data applications which benefit from a datagram service can be effectively supported by this technique. However, datagram traffic is characterized by the fact that each datagram can be viewed as a connection and requires the computation of a path. Each packet is routed through the network as a self contained unit and is independent of all other packets. The key point for the source node is to determine for each datagram the optimal route for the shortest lapse of time.
Label Swapping
Label Swapping is a particular implementation of Distributed Routing for connection oriented networks. These networks typically multiplex many connections (or sessions) on a link using some form of logical "channel". Each packet sent on the link has a header which includes an arbitrary number identifying which logical connection that this packet belongs to. For example, each packet can contain in its routing field a label that will be used by the intermediate nodes to identify the transmission link the packet should be routed over. When a packet arrives at a node, the label is extracted from its header, and used to index a routing table that provides a new label along with a link address. The new label is over written on the old label, and the packet is forwarded using the link address. The information in the routing table is updated at the connection set up time. Each node on a path selects a label for each direction of the connection, and sends it to the neighboring node. The call set up and the resource reservation process comprises the following steps:
A connection request is specified by the user via a set of parameters including origin and destination network address and data flow characteristics,
The path determination is made by the source node from its local routing Topology Database
The route reservation is sent out in a special message to the specified nodes. The message, which is usually routed according to the previously described Source Routing technique, signals the nodes to set up their connection tables and to reserve their resources to provide the level of service required by the traffic type (for example, a bandwidth reservation on each of the links of the path).
The tables update reflects the changes in the availability of the network resources. The information is sent to every node in the network.
The Label Swapping technique requires that the connection tables be set up and maintained dynamically. That means that when a new connection is established or an old one is terminated the tables are updated (the database of network topology can of course be maintained quite separately). This is possible if the connection set up is relatively infrequent and is not too time critical. This restriction makes datagram transport quite inefficient. However, connections that require very short packets, like real-time voice connections, can be effectively supported by this technique, because of the low packet overhead. Once the connection is established, there is no need to place a destination address in the header every time a packet is sent. All is needed is a field to specify which connection is to be used for this packet.
Path Selection Criterion
One of the major criterion for selecting paths between nodes in packet networks is the minimum hop count and minimum path length. The hop count is the number of links used to construct the path between the two end nodes. The path length is a function of the overall transmission delay imposed by the path between the two end nodes. In most high speed networks, the delay (path length) is not a major consideration since the worst-case delay through such networks is nearly always acceptable. The hop count, however, is a direct measure of the amount of resources required to implement a given path and hence is of considerable importance in selecting paths. It is to be noted that a selected path need not be a minimum hop count path since congestion on the network links may force the choice of a larger hop count path. However, such longer alternate paths cannot be allowed to grow without limit since inordinate amours of network resources might be committed to one path, resulting in further congestion for other paths and forcing yet longer hop count paths to be selected for yet other connections. The long term network throughput could thereby be adversely affected. The problem, then, is to select a path between an origin node and a destination node which has a hop count, and a path length, which does not utilize an inordinate amount of network resources.
Key Requirements
The Distributed Routing mechanism in large and high speed packet switching networks supporting both connection oriented and connectionless routing modes implies some requirements in terms of performance and resource consumption which can be summarized as follows:
the source node (or the node providing the route calculation for the source node) must be able to decide where to route an incoming packet in a very short portion of time (the computation must be sufficiently rapid to compute an optimum path for each connection request)
the switching time in the intermediate nodes must be minimized, (minimum processing time)
the network resources along the selected path must be optimized according to the criterion of the minimum hop count.
Control messages must be limited as much as possible to not overload the network.
In high speed networks the cost for updating the routing tables generated by the exchange of control messages is not critical so long as this can be performed before the connection set up. The very high link throughput authorizes the interchanging of routing information without creating a significant burden on the communication links themselves. These considerations suggest a better access and use of the routing tables maintained within the nodes without sacrificing the criterion of optimal path contrary to the Hierarchical Routing method proposed by L. Kleinrock and F. Kamoun.